package gitdemo1.git3.list;

import java.util.List;
import java.util.Stack;

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

      public static void main(String[] args) {
        ListNode node6 = new ListNode(6, null);
        ListNode node5 = new ListNode(4, node6);
        ListNode node4 = new ListNode(3, node5);
        ListNode node3 = new ListNode(6, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode listNode = removeElements(node1, 6);

      }


      public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode node = new ListNode(-1, head);
        ListNode pre=node,rear=node;
        while (n>0){
          rear=rear.next;
          n--;
        }
        while (rear.next!=null){
          rear=rear.next;
          pre=pre.next;
        }
        pre.next=pre.next.next;

        return node.next;

      }
  public ListNode swapPairs(ListNode head) {
    ListNode node = new ListNode(-1, head);
    ListNode pre=node;
    while(pre.next!=null&&pre.next.next!=null){
      ListNode temp = head.next.next;//保存节点3
      pre.next=head.next;
      head.next.next=head;
      head.next=temp;
      pre=head;
      head=temp;

    }

    return node.next;

  }

  public ListNode swapPairs1(ListNode head) {

    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode prev = dummyNode;

    while (prev.next != null && prev.next.next != null) {
      ListNode temp = head.next.next; // 缓存 next
      prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
      head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
      head.next = temp;               // 将head 的 next 接上缓存的temp
      prev = head;                    // 步进1位
      head = head.next;               // 步进1位
    }
    return dummyNode.next;
  }

    public ListNode middleNode(ListNode head) {
      ListNode slow=head,p=head;
      while(p.next!=null&&p.next.next!=null){
        slow=slow.next;
        p=p.next.next;
      }
      if(p.next==null){
        return slow;
      }else {
        return slow.next;
      }


    }


      public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
          return head;
        }
        ListNode node = new ListNode(-1,head);

        ListNode p=head,pre=node;
        while (p!=null){
          if(p.val==val){
            pre.next=p.next;
          }
          pre=pre.next;
          p=p.next;
        }
        return node.next;


      }

  public  ListNode reverseList1(ListNode head) {
    if(head==null) {return null;}

    ListNode temp=head;
    ListNode end=null;
    while(temp.next!=null ){

      //当前节点
      ListNode cur=temp;
      //往前指
      cur.next=end;
      //保存下一个节点
      end =temp;
      temp=temp.next;
    }
    temp.next=end;

    return temp;
  }

  public  boolean isPalindrome(ListNode head) {
    //利用栈来写
    Stack<ListNode> stack = new Stack<>();
    ListNode temp = head;
    //先压入栈里去
    while (temp != null) {
      stack.add(temp);
      temp = temp.next;
    }
    //拿出来比较
    while (!stack.isEmpty()) {
      if (stack.pop().val != head.val) {
        return false;

      }
      head = head.next;

    }

    return true;


  }

  public ListNode reverseList(ListNode head) {
    if(head==null||head.next==null){
      return head;
    }
    //把之前,当前和下一个给记录下来
    ListNode pre=null;
    ListNode next;
    ListNode cur=head;
    while(cur!=null){
      //记录下一个
      next=cur.next;
      //当前指向之前的
      cur.next=pre;
      //现在的变成之前的
      pre=cur;
      //下一个节点继续
      cur=next;
    }

    return pre;
  }

  public ListNode hasCycle(ListNode head) {
      if(head==null||head.next==null||head.next.next==null){
        return null;
      }
      //定义快慢指针
      ListNode slow=head.next;
      ListNode fast=head.next.next;


      while(fast!=slow){
        if(fast.next==null||fast.next.next==null){
          return null;
        }
        slow=slow.next;
        fast=fast.next.next;
      }
      fast=head;
      while(fast!=slow){
        fast=fast.next;
        slow=slow.next;
      }


      return fast;
  }

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1==null&&list2==null){
      return null;
    }
    if(list1==null){
      return list2;
    }
    if(list2==null){
      return list1;
    }
    ListNode cur=null;
    ListNode head=null;
    head.next=cur;
    //当他们都不为空时
    while(list1!=null&&list2!=null){
      if(list1.val<=list2.val){
        cur.next=list1;
        cur=cur.next;
        list1=list1.next;
      }else {
        cur.next=list2;
        cur=cur.next;
        list2=list2.next;
      }

    }
    if(list1==null){
      cur.next=list2;
    }
    if(list2==null){
      cur.next=list1;


    }



    return cur;
  }

  public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head==null){
      return null;
    }
    ListNode cur=head;
    ListNode s=head;
    ListNode f=head;
    while(n>0){
      f=f.next;
      n--;
    }
    if(f==null){
      return null;
    }
    while(f.next!=null){
      f=f.next;
      s=s.next;
    }
    s.next=f;

    return cur;
  }



}
